package leetcode.leetcode144;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/26
 *
 * 二叉树前序遍历
 * 94为中序遍历
 */
public class Leetcode144 {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                list.add(curr.val); // 在这里添加为前序遍历
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode pop = stack.pop();
                // list.add(pop.val); 在这里添加为中序遍历
                curr = pop.right;
            }
        }
        return list;
    }

    /**
     * 后序遍历
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                //list.add(curr.val); // 在这里添加为前序遍历
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    list.add(pop.val);
                } else {
                    curr = peek.right;
                }
            }
        }
        return list;
    }

    // 通用模版
    public List<Integer> preorderTraversal3(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                //list.add(curr.val); // 在这里添加为前序遍历
                // 待处理左子树
                curr = curr.left;
                //list.add(peek.val); // 在这里添加为中序遍历
            } else {
                TreeNode peek = stack.peek();
                // 没有右子树
                if (peek.right == null) {
                    pop = stack.pop();
                    //list.add(pop.val); // 在这里添加为后序遍历
                // 右子树处理完成
                } else if (peek.right == pop) {
                    pop = stack.pop();
                    //list.add(pop.val); // 在这里添加为后序遍历
                } else {
                // 待处理右子树
                    //list.add(peek.val); // 在这里添加为中序遍历
                    curr = peek.right;
                }
            }
        }
        return list;
    }
}
